import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shuang
 * @date 2022/5/9 11:46
 * 942. 增减字符串匹配
 * https://leetcode.cn/problems/di-string-match/
 */
public class Solutions_942 {
    public static void main(String[] args) {
        String s1 = "IDID";  // output: {0, 4, 1, 3, 2}
        String s2 = "III";  // output: {0, 1, 2, 3}
        String s3 = "DDI";  // output: {3, 2, 0, 1}

        List<String> inputs = new ArrayList<>();
        inputs.add(s1);
        inputs.add(s2);
        inputs.add(s3);

        Solutions_942 obj = new Solutions_942();
        for (String input : inputs) {
            int[] result = obj.diStringMatch(input);
            System.out.println(Arrays.toString(result));
        }
    }

    /**
     * 双指针 + 贪心
     * @param s
     * @return
     */
    public int[] diStringMatch(String s) {
        char[] sarr = s.toCharArray();
        int len = sarr.length;
        int[] res = new int[len + 1];
        int left = 0, right = len;
        for (int i = 0; i < len; i++) {
            if (sarr[i] == 'I') {
                res[i] = left;
                left ++;
            } else {
                res[i] = right;
                right --;
            }
        }
        // 补充最后一位
        if (res[res.length - 1] == left) {
            res[res.length - 1] = right;
        } else {
            res[res.length - 1] = left;
        }
        return res;
    }
}

